package main

import (
	"fmt"
	"sort"
)

/**
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2.5 MB, 在所有 Go 提交中击败了87.16%的用户
 */
var ans [][]int
var path []int

func combinationSum2(c []int, target int) [][]int {

	sort.Slice(c, func(i, j int) bool {
		return c[i] < c[j]
	})

	ans = [][]int{}
	path = []int{}
	dfs(c, target, 0)
	return ans
}

func dfs(c []int, target int, u int) {

	if target == 0 {
		t := make([]int, len(path))
		copy(t, path)
		ans = append(ans, t)
		return
	}
	if u == len(c) { return }

	k := u + 1
	for k < len(c) && c[k] == c[u] { k++ }
	cnt := k - u

	for i := 0; c[u] * i <= target && i <= cnt; i++ {
		dfs(c, target - c[u] * i, k)
		path = append(path, c[u])
	}

	for i := 0; c[u] * i <= target && i <= cnt; i++ {
		path = path[:len(path) - 1]
	}
}

func main() {

	c := []int{10, 1, 2, 7, 6, 1, 5}
	fmt.Println(combinationSum2(c, 8))
}
